package leetcode;

public class MaxXOROfTwoNumbers {

    private class Trie {
        Trie[] children;
        public Trie() {
            children = new Trie[2];
        }
    }
    
    public int findMaximumXOR(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        Trie root = new Trie();
        for(int i= 0; i < nums.length; i++){
            Trie node = root;
            for(int j = 31; j >= 0; j--){
                int curBit = (nums[i] >>> j) & 1;
                if(node.children[curBit] == null){
                    node.children[curBit] = new Trie();
                }
                node = node.children[curBit];
            }
        }
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
			Trie node = root;
			int curValue = 0;
			for (int i = 31; i >= 0; i--) {
				int curBit = (num >>> i) & 1;
				//如果与curBit对应的
				if(node.children[curBit ^ 1] != null) {
					curValue = (1 << i) + curValue;
					//比如当前num是A，node.children[curBit ^ 1] != null的那位数为B
					//此时为了求最大的亦或，肯定需要的是切换到B的node表示中
					node = node.children[curBit ^ 1];
				}else{
					node = node.children[curBit];
				}
			}
			max = Math.max(max, curValue);
		}
        return max;
    }
    
	public static void main(String[] args) {
		
	}
}
